#wi
#vi
#
#目标函数:Max(sum(vi*xi))
#
#约束条件:sum(wi*xi)<=C
#         0<=xi<=1
C = 50
w = [10,20,30]
v = [60,100,120]
# C = 150
# w = [35,30,60,50,40,10,25]
# v = [10,40,30,50,35,40,30]
# init v/w
v_w = []
for i in range(len(w)):
    v_w.append(v[i]/w[i])

# 从大到小排序，并且返回响应的索引值list
index = sorted(range(len(v_w)), key=lambda k: v_w[k],reverse=True)


answer = []

# greedy select
def greedy_select(v_w,C):
    left_weight = C 
    all_value = 0
    for i in (index):
        # append 
        left_weight = left_weight - w[i]
        if (left_weight) >= 0:
            answer.append((i+1,1)) # 装第几个箱子，装多少
            all_value = all_value + v[i]
        else:
            left_weight = left_weight + w[i] # 加回来
            answer.append((i+1,left_weight/w[i])) # 装第几个箱子，装多少
            all_value = all_value + v[i] * (left_weight/w[i])
            break
    print('我选择的方案(第n个箱子，装的个数)',answer)
    print('最优解 =',all_value)
greedy_select(v_w,C)

